package main.面试金典第六版;

import java.util.*;

public class Interview08 {
    public static void main(String[] args) {
        System.out.println("面试题08.01：三步问题");
        System.out.println("面试题08.02：迷路的机器人");
        System.out.println("面试题08.03：魔术索引");
        System.out.println("面试题08.04：幂集");
        System.out.println("面试题08.05：递归乘法");
        System.out.println("面试题08.06：汉诺塔问题");
        System.out.println("面试题08.07：无重复字符串的排列组合");
        System.out.println("面试题08.08：有重复字符串的排列组合");
        System.out.println("面试题08.09：括号");
        System.out.println("面试题08.10：颜色填充");
        System.out.println("面试题08.11：硬币");
        System.out.println("面试题08.12：八皇后");
        System.out.println("面试题08.13：堆箱子");
        System.out.println("面试题08.14：布尔运算");
    }
}

class Interview_08_01{
    public int waysToStep(int n) {
        int MOD=1000000007;
        long first=1,second=2,third=4,forth=0;
        if (n==1) return 1;
        else if (n==2) return 2;
        else if (n==3) return 4;
        for (int i=4;i<=n;i++) {
            forth=(first+second+third)%MOD;//累加前三种
            first=second%MOD;
            second=third%MOD;
            third=forth%MOD;
        }
        return (int)forth%MOD;
    }
}

class Interview_08_02{
    List<List<Integer>> temp,res;
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        temp = new ArrayList();
        res = new ArrayList();
        boolean[][] visted = new boolean[obstacleGrid.length][obstacleGrid[0].length];
        process(obstacleGrid, 0, 0, visted);
        return res;
    }

    public void process(int[][] grids, int r, int c, boolean[][] visted) {
        if (r < 0 || r >= grids.length || c < 0 || c >= grids[0].length || grids[r][c] == 1) return;
        if (visted[r][c]) {
            grids[r][c] = 1;
            return;
        }
        visted[r][c] = true;
        temp.add(new ArrayList(Arrays.asList(r, c)));
        if (r == grids.length - 1 && c == grids[0].length - 1) {
            res = new ArrayList(temp);
            return;
        }
        process(grids, r, c + 1, visted);
        process(grids, r + 1, c, visted);
        temp.remove(temp.size() - 1);
    }
}

class Interview_08_03{
    public int findMagicIndex(int[] nums) {
        int result=-1;
        for (int i=0;i< nums.length;i++) {
            if (nums[i]==i) {
                result=i;
                break;
            }
        }
        return result;
    }
}

class Interview_08_04{
    List<List<Integer>> list=new ArrayList<>();
    public void process(int[] nums,int start,List<Integer> curList){
        if (start>= nums.length){
            list.add(curList);
            return;
        }
        List<Integer> tempList=new ArrayList<>(curList);
        tempList.add(nums[start]);
        list.add(tempList);
        for (int i=start+1;i< nums.length;i++){
            process(nums,i,tempList);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> tempList=new ArrayList<>();
        list.add(tempList);
        for (int i=0;i< nums.length;i++){//以i开始的所有子集
            process(nums,i,tempList);
        }
        return list;
    }
}

class Interview_08_05{
    int numA=0;
    Map<Integer,Integer> map;
    public int process(int num) {
        if (num==1) return numA;//base case
        if (map.containsKey(num)) return map.get(num);//缓存
        int total=process(num/2)+process(num-num/2);
        map.put(num,total);
        return total;
    }
    public int multiply(int A, int B) {
        numA=A;
        map=new HashMap<>();
        int total=process(B);
        return total;
    }
}

class Interview_08_06{
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        for (int i=0;i<A.size();i++) C.add(A.get(i));
        A.clear();
    }
}

class Interview_08_07{
    boolean[] flags;
    char[] str;
    List<String> list;
    public void process(String lastStr) {
        if (lastStr.length()==str.length) {//结束
            list.add(lastStr);
            return;
        }
        for (int i=0;i< str.length;i++) {
            if (!flags[i]) {
                String curStr=lastStr+str[i];//使用
                flags[i]=true;
                process(curStr);
                flags[i]=false;//撤销
            }
        }
    }
    public String[] permutation(String S) {
        str=S.toCharArray();
        flags=new boolean[str.length];
        list=new ArrayList<>();
        for (int i=0;i< str.length;i++) {
            String curStr=""+str[i];//使用
            flags[i]=true;
            process(curStr);
            flags[i]=false;//撤销
        }
        String[] result=new String[list.size()];
        for (int i=0;i< list.size();i++) result[i]=list.get(i);
        return result;
    }
}

class Interview_08_08{
    boolean[] flags;
    char[] str;
    Set<String> set;
    public void process(String lastStr) {
        if (lastStr.length()==str.length) {//结束
            set.add(lastStr);
            return;
        }
        for (int i=0;i< str.length;i++) {
            if (!flags[i]) {
                String curStr=lastStr+str[i];//使用
                flags[i]=true;
                process(curStr);
                flags[i]=false;//撤销
            }
        }
    }
    public String[] permutation(String S) {
        str=S.toCharArray();
        flags=new boolean[str.length];
        set =new HashSet<>();
        for (int i=0;i< str.length;i++) {
            String curStr=""+str[i];//使用
            flags[i]=true;
            process(curStr);
            flags[i]=false;//撤销
        }
        String[] result=new String[set.size()];
        int i=0;
        for (String str:set) {
            result[i]=str;
            i++;
        }
        return result;
    }
}

class Interview_08_09{
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        process(res, n, n, new StringBuilder());
        return res;
    }
    public void process(List<String> res, int left, int right, StringBuilder builder) {
        if (right == 0) {
            res.add(builder.toString());
            return;
        }
        if (left > 0) {
            StringBuilder tmpBuilder = new StringBuilder(builder.toString());
            process(res, left - 1, right, tmpBuilder.append("("));
        }
        if (left < right) {
            StringBuilder tmpBuilder = new StringBuilder(builder.toString());
            process(res, left, right - 1, tmpBuilder.append(")"));
        }
    }
}

class Interview_08_10{
    int[][] image;
    int targetColor;
    public void process(int row,int col,int newColor) {
        image[row][col]=newColor;
        if (row-1>=0&&image[row-1][col]==targetColor&&image[row-1][col]!=newColor) process(row-1,col,newColor);//上
        if (row+1<image.length&&image[row+1][col]==targetColor&&image[row+1][col]!=newColor) process(row+1,col,newColor);//下
        if (col-1>=0&&image[row][col-1]==targetColor&&image[row][col-1]!=newColor) process(row,col-1,newColor);//左
        if (col+1<image[0].length&&image[row][col+1]==targetColor&&image[row][col+1]!=newColor) process(row,col+1,newColor);//右
    }
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        this.image=image;
        targetColor=image[sr][sc];
        process(sr,sc,newColor);
        return this.image;
    }
}

class Interview_08_11{
    public int waysToChange(int n) {
        int[] coins={1,5,10,25};
        long[] dp=new long[n+1];
        dp[0]=1;
        for (int num : coins) {
            for (int i=num;i<=n;i++) {
                dp[i]=dp[i-num]+dp[i];
            }
        }
        return (int) (dp[n]%1000000007);
    }
}

class Interview_08_12{
    List<List<Integer>> indexList;
    int n;
    public List<String> process3(List<Integer> position,int n) {//根据方案得到字符串
        List<String> result=new ArrayList<>();
        for (int index : position) {
            StringBuffer stringBuffer=new StringBuffer();
            for (int i=0;i<n;i++) stringBuffer.append(".");
            stringBuffer.setCharAt(index,'Q');
            result.add(stringBuffer.toString());
        }
        return result;
    }
    public boolean process2(List<Integer> lastList,int index) {//判断该位置是否满足条件
        if (lastList.contains(index)) return false;//存在同一列
        int curLevel=lastList.size();
        for (int i=0;i<lastList.size();i++) {//判断对角线
            int col=lastList.get(i);
            double k=((col-index)*1.0)/((i-curLevel)*1.0);
            if (Math.abs(k)==1) return false;
        }
        return true;
    }
    public void process1(List<Integer> lastList,int level) {//逐层遍历
        List<Integer> curList=new ArrayList<>(lastList);
        if (level>n) {//最后一层完结
            indexList.add(curList);
            return;
        }
        for (int i=0;i<n;i++) {
            if (process2(curList,i)) {
                curList.add(i);
                process1(curList,level+1);//进入下一层
                curList.remove(curList.size()-1);
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        indexList=new ArrayList<>();
        this.n=n;
        List<Integer> curList=new ArrayList<>();
        process1(curList,1);
        List<List<String>> result=new ArrayList<>();
        for (List<Integer> curPosition : indexList) {
            List<String> curString=process3(curPosition,n);
            result.add(curString);
        }
        return result;
    }
}

class Interview_08_13{
    public int pileBox(int[][] box) {
        Arrays.sort(box, (box1, box2) -> box1[0] - box2[0]);
        int[] dp = new int[box.length];
        int totalH = 0;
        for (int i = 0; i < box.length; i++) {
            dp[i] = box[i][2];
            for (int j = i - 1; j >= 0; j--) {
                if (box[j][0] < box[i][0] && box[j][1] < box[i][1] && box[j][2] < box[i][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + box[i][2]);
                }
            }
            totalH = Math.max(totalH, dp[i]);
        }
        return totalH;
    }
}

class Interview_08_14{
    public int countEval(String s, int result) {
        int n=(s.length()+1)/2;
        int length=s.length();
        int[][][] dp=new int[length][length][2];//dp[i][j][r]索引i到j为r的个数
        for(int i=0;i<length;i+=2){//初始化
            if(s.charAt(i)=='1')dp[i][i][1]=1;
            if(s.charAt(i)=='0')dp[i][i][0]=1;
        }
        for(int d=2;d<length;d+=2){
            for(int i=0;i+d<length;i++){//距离
                for(int k=0;k<d;k+=2){//对于每段进行遍历
                    char ch=s.charAt(i+k+1);
                    if(ch=='&'){
                        dp[i][i+d][1]+=dp[i][i+k][1]*dp[i+k+2][i+d][1];
                        dp[i][i+d][0]+=dp[i][i+k][0]*dp[i+k+2][i+d][1]+dp[i][i+k][1]*dp[i+k+2][i+d][0]+dp[i][i+k][0]*dp[i+k+2][i+d][0];
                    }
                    if(ch=='|'){
                        dp[i][i+d][0]+=dp[i][i+k][0]*dp[i+k+2][i+d][0];
                        dp[i][i+d][1]+=dp[i][i+k][1]*dp[i+k+2][i+d][0]+dp[i][i+k][0]*dp[i+k+2][i+d][1]+dp[i][i+k][1]*dp[i+k+2][i+d][1];
                    }
                    if(ch=='^'){
                        dp[i][i+d][0]+=dp[i][i+k][0]*dp[i+k+2][i+d][0]+dp[i][i+k][1]*dp[i+k+2][i+d][1];
                        dp[i][i+d][1]+=dp[i][i+k][1]*dp[i+k+2][i+d][0]+dp[i][i+k][0]*dp[i+k+2][i+d][1];
                    }
                }
            }
        }
        return dp[0][length-1][result];
    }
}